1. Field of the Invention
The present invention generally relates to a method and apparatus for navigating a graph of data items in a data processing system utilizing a visual display and, more particularly, to a method and apparatus for navigating a graph of data items where the data items are displayed in successive outer portions of a geometric shape, such as successive circular shaped portions, the center portion showing a current position and successive outer portions showing optional paths for navigation.
2. Background Description
Information may be graphically displayed on computer screens or other means of visual display in many different manners. These graphical displays include simple tree diagrams to menu driven displays similar to those currently used in many programs, such as Lotus WordPro.RTM..
Typically, graphically based information often consists of a set of related data items referred to as "nodes". The nodes are related to one another through another type of data item called "arcs". The arcs connect the nodes to one another and may define the relationship between the nodes. In the case when two nodes are connected by an arc, the nodes are referred to as "neighbors". In most graphical cases, the arcs are depicted as lines having arrows pointing in a predefined direction to a node. In this case, when the arcs connect two nodes that have a special relationship to one another, the arcs are then often referred to as "directed" arcs.
The nodes may be related to one another (via arcs) such that one node may bring the user to a second and related node. For example, a family tree may include several generations, for example, a parent (e.g., a first node) and a child (e.g., a second node). Between the parent and the child nodes is an arc that defines the relationship between the parent and the child (i.e., the child is a direct descendant of the parent). In the above example, the arc may have an arrow pointing from the most recent generation (e.g., child) to the next preceding generation (e.g., parent). By proceeding through several nodes, the user ultimately attains the required information, such as the name of a great grandfather.
By way of further example, the arcs may also depict a qualitative measure, in addition to depicting the relationship between adjacent nodes. In other words, nodes of a graph may represent the parts of some physical assemblage, and the arcs connecting the nodes may represent qualitative information about the relationships between the nodes. For example, a graph may be drawn where each node represents a city. Arcs may then connect the cities, where the arcs represent both roads between adjacent cities (e.g., relationship), while at the same time referring to data holding distances between the adjacent cities (e.g., qualitative measure).
However, representing graphs on a visual display, such as a computer screen, has posed many problems that have been difficult to overcome. As previously described, graphs are usually displayed in a fairly conventional manner using small circles to represent nodes, and lines to represent arcs. The problem with this representation is that it does not scale well to display technology, and even a modest size graph would overwhelm a user in its amount of data.
Also, many graphs do not lend themselves to a "natural" layout, due to the nature of the information being graphically displayed. For example, a graph of a local telephone network would consist of thousands and maybe millions of arcs and nodes. This would lead to a very complex graphical representation of data items that would be almost impossible to decipher by a user searching such information. In these instances, automating a graph layout is typically difficult and to some degree unpredictable except for the imposition of general constraints (e.g., minimizing the number of arc crossings). However, even some complex graphical representations, such as the above example of the local telephone network, would still provide practically no useful graphical information after automation.
In addition to the above mentioned shortcomings of present graphical representations, there are many instances a user desires to not only interact with an entire graph, but at times to equally interact with only a small portion of the graphical information. In the latter scenario the user is typically concerned with interacting only with a certain locale of the graph in order to glean certain specific information.
In the case where only a small locale of the graph is desired (e.g., immediate neighbors), many graphical systems utilize zooming control. However, zoom control does not work uniformly in that it is easy to zoom to locales with neighbors that cannot easily be rendered with the focus of the locale. This all depends on the graph layout itself which by virtue of its computational complexity cannot easily address locality constraints across the entire graph.